package com.hc.programming.tree;

import lombok.Data;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

@Data
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * 转成树
     */
    public static TreeNode tree(List<Integer> nodes) {
        return tree(nodes.toArray(new Integer[0]));
    }

    public static TreeNode tree(Integer[] nodes) {
        if (nodes == null || nodes.length == 0) return null;
        TreeNode root = new TreeNode(nodes[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int idx = 1;
        while (!queue.isEmpty() && idx < nodes.length) {
            TreeNode node = queue.poll();

            // 构建左子节点
            if (nodes[idx] != null) {
                node.left = new TreeNode(nodes[idx]);
                queue.offer(node.left);
            }
            idx++;

            // 构建右子节点
            if (idx < nodes.length && nodes[idx] != null) {
                node.right = new TreeNode(nodes[idx]);
                queue.offer(node.right);
            }
            idx++;
        }
        return root;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("{");
        sb.append("val: ").append(val);
        sb.append(", high: ").append(getHeight(this));
        if (left != null) sb.append(", left: ").append(left);
        if (right != null) sb.append(", right: ").append(right);
        sb.append("}");
        return sb.toString();
    }

    public static int getHeight(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }
}